package leetcode.offer;

/**
 * ClassName: Fib
 * Description:leetcode-剑指offer 10 - I.斐波那切数列
 * date: 2021-11-03 10:19
 *
 * @author liyifan
 */
public class Fib {
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2)
            return n;

        long p = 0;
        long q = 0;
        long r = 1;
        for (int i = 2;i <= n;i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return (int) (r % MOD);
    }

    //todo 矩阵快速幂
}
